package levelOrder

import "container/list"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/*
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
广度优先搜索
使用队列
*/
func levelOrder(root *TreeNode) [][]int {
	queue := list.New()
	var ans [][]int
	if root == nil {
		return ans
	}
	queue.PushBack(root)
	ans = append(ans, []int{root.Val})
	index := 0
	for queue.Len() > 0 {
		// 每层的结点数
		num := queue.Len()
		var v []int
		// 外层的每次循环都是一层
		for i := 0; i < num; i++ {
			e := queue.Front()
			queue.Remove(e)

			node := e.Value.(*TreeNode)
			if node.Left != nil {
				v = append(v, node.Left.Val)
				queue.PushBack(node.Left)
			}
			if node.Right != nil {
				v = append(v, node.Right.Val)
				queue.PushBack(node.Right)
			}
		}
		if len(v) > 0 {
			ans = append(ans, v)
		}
		index++
	}
	return ans
}
